package linked_list;

public class Josepfu {
    public static void main(String[] args) {
        Boy n1 = new Boy(1);
        Boy n2 = new Boy(2);
        Boy n3 = new Boy(3);
        Boy n4 = new Boy(4);
        Boy n5 = new Boy(5);
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(n1);
        circleSingleLinkedList.add(n2);
        circleSingleLinkedList.add(n3);
        circleSingleLinkedList.add(n4);
        circleSingleLinkedList.add(n5);
        circleSingleLinkedList.show();
        circleSingleLinkedList.josepfuSolver(1, 2);
    }
}

class CircleSingleLinkedList {
    private Boy head = new Boy(0);

    // 在最后一个元素和第一个元素(head指向的元素)之间添加元素
    public void add(Boy boy) {
        // 找到链表的最后
        Boy temp = head.next;
        while (true) {
            if (temp == null) {
                // 如果链表为空
                head.next = boy;
                boy.next = boy;
                break;
            } else if (temp.next == head.next) {
                // 如果链表长度大于1，且temp指向最后一个节点
                boy.next = head.next;
                temp.next = boy;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 求解约瑟夫问题
     * 
     * @param k 从第几个小孩开始报数
     * @param m 报到几出列
     */
    public void josepfuSolver(int k, int m) {
        // 先将cur指向链表末尾
        Boy cur = head.next;
        while (cur.next != head.next) {
            cur = cur.next;
        }
        // 让cur和head一起向前移动k-1次
        for (int i = 0; i < k - 1; i++) {
            cur = cur.next;
            head.next = head.next.next;
        }
        // 再将cur和head一起向前移动
        while (cur != head.next) {
            int num = 0;
            while (num++ != m - 1) {
                cur = cur.next;
                head.next = head.next.next;
            }
            // 此时head指向的节点即为出列的节点
            System.out.println(head.next.no);
            head.next = head.next.next;
            cur.next = head.next;
        }
        System.out.println(cur.no);
    }

    // 输出链表
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Boy temp = head.next;
        System.out.println(temp.toString());
        temp = temp.next;
        while (temp != head.next) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

// 节点定义
class Boy {

    // data域
    public int no;

    // 指针域
    public Boy next;

    public Boy(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Boy [no=" + no + "]";
    }
}